1766D - Lucky Chains - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define pb push_back

const int INF = 1e7;
ll t, ok[INF+10], a, b, ans;
vector<ll> pr;

ll gcd(ll a,ll b){
  if (b == 0) return a;
  return gcd(b, a % b);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
  for(ll i = 1; i<= INF; i++){
    ok[i] = i;
  }
  for(ll i = 2; i<= INF; i++){
    if(ok[i] == i){
      for(ll j = i*i; j<= INF; j+= i){
        ok[j] = ok[i];
      }
    }
  }
  cin >> t;
  while(t--){
    cin >> a >> b;
    ll ogt = b-a;
    if(ogt == 1){
      cout << -1 << '\n';
      continue;
    }
    if(gcd(a, b) != 1){
      cout << 0 << '\n';
      continue;
    }
    while(ogt > 1){
      pr.pb(ok[ogt]);
      ogt /= ok[ogt];
    }
    ans = 1e9;
    for(auto i : pr){
      ans = min(ans, i-(a%i));
    }
    cout << ans << '\n';
    pr.clear();
  }
}